Binary Trees: Definitions and Properties

A Binary Tree (BT) is a hierarchical data structure where each node has at most two children: a left child and a right child. They are crucial for implementing efficient data storage, search algorithms, and representing computational structures like Abstract Syntax Trees (ASTs).

Key Types & Property

Strict/Full Binary Tree: Every non-leaf node has exactly two children.
Perfect Binary Tree: A full tree where all leaves are at the same level.

Crucial Node Relationship (Strict Binary Trees):

If $N$ is the total number of nodes, $L$ is the number of leaf nodes, and $I$ is the number of internal (non-leaf) nodes:

N = 2L - 1 \quad \text{AND} \quad I = L - 1

If a strict tree has 10 internal nodes ( $I=10$ ), it must have 11 leaf nodes ( $L=11$ ), totaling $N=21$ nodes.

Height and Node Capacity

The height ( $H$ ) of a tree (maximum number of edges from the root to the deepest leaf) dictates its maximum capacity:

Level ( $k$ , Root=0)	Max Nodes	Total Max Nodes (Perfect Tree)
0 (Root)	$2^0 = 1$	1
$k$	$2^k$	$2^{k+1} - 1$
$H$	$2^H$	$N_{max} = 2^{H+1} - 1$

Optimal Height: For a tree with $N$ nodes, the minimum possible height (achieved by a balanced tree) is:

H_{\min} = \lceil \log_2(N+1) \rceil - 1

📝 Checkpoint: Binary Tree Structure

1. A programmer constructs a strict binary tree. If it has 15 non-leaf (internal) nodes, how many total nodes ( $N$ ) does it contain?

A) 31
B) 30
C) 16
D) 29

2. Which property best describes a Perfect Binary Tree?

A) Every node has at most one child.
B) It is a full tree where all leaves are at the same depth.
C) The tree is skewed to the left.
D) Only the root node can have two children.

3. What is the maximum number of nodes in a perfect binary tree with a height of 3?

A) 7
B) 8
C) 15
D) 16

4. In a binary tree, what does the 'depth' of a node refer to?

A) The longest path from the node to a leaf.
B) The total nodes in its subtree.
C) The number of edges from the root to that node.
D) The number of children the node has.

KEY TIPS

💡 Terminology

Understanding Depth vs. Height

Depth (of Node X): The distance (number of edges) from the Root to node X.
Height (of Node X): The length of the longest path from node X down to any leaf.
Height (of Tree): The height of the root node.

Edge Case Reminder

A tree with only one node (the root) has N=1 and L=1. The strict relationship holds:

1 = 2(1) - 1

. The height is 0.